package com.example.leetcode.trainingcamp.week3.Thursday;

import java.util.Stack;

/***
 * 栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sort-of-stacks-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SortedStack {

    private final Stack<Integer> stack;

    private final Stack<Integer> temp;



    public SortedStack() {
        stack = new Stack<>();
        temp = new Stack<>();
    }

    public void push(int val) {
        if (stack.isEmpty()){
            stack.push(val);
        }else {
            Integer peek = stack.peek();
            if (peek >= val){
                stack.push(val);
            }else {
                while (!stack.isEmpty() && stack.peek() < val){
                    temp.push(stack.pop());
                }
                stack.push(val);
                while (!temp.isEmpty()){
                    stack.push(temp.pop());
                }
            }
        }
    }

    public void pop() {
        if (!stack.isEmpty()){
            stack.pop();
        }
    }

    public int peek() {
        if (stack.isEmpty()){
            return -1;
        }
        return stack.peek();
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }
}


class TestSortStack{
  public static void main(String[] args) {
    SortedStack stack = new SortedStack();
    stack.pop();
    stack.pop();
    stack.push(1);
    stack.pop();
    System.out.println(stack.isEmpty());
  }
}